"""
https://leetcode.cn/problems/reorder-list/description/

143. 重排链表
中等
相关标签
premium lock icon
相关企业
给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例 1：



输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：



输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
 

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional
from list_node import ListNode,create_list_node,calc_arr


class Solution:
    """
    最简单的一种方法：把所有节点都放在数组中，之后操作数组对节点进行swap。
    之后根据最终数组重构一个新的链表。此方法实现起来较为简单，故忽略。

    另一种方式，先遍历一遍链表，获取链表长度。进而预测出中间节点（也是实际的最后节点）。
    通过遍历拿到中间节点，再从该节点后数据，构建为一个逆向的新节点数组。
    之后遍历原链表节点和新逆向链表节点，各自构建出最终结果。

    中间节点的计算：
    链表长度为n
    如果n为奇数，则中间节点必定是中心节点，即数学上的：(n+1)/2，也是计算机中的：n//2
    如果n为偶数，则中间节点为中间靠后的那个节点。这是因为原始的第一个节点在结果链表中也是第一个，因此导致后半段转为逆向链表时，后半段的第一个节点，是结果链表的最后一个节点。
    需要转为逆向链表的原始首节点，也是该节点（实际上如果是中间靠前的节点，对结果也没有影响）。
    该位置，在数学上位于：n/2+1，在计算机中位置，位于：n//2
    

    """
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return
        root=ListNode(0,head)
        # 获取节点长度
        link_len=0
        old_temp=root
        while old_temp.next:
            link_len+=1
            old_temp=old_temp.next
        
        # 获取中间节点(必定存在)
        mid_idx=(link_len-1)//2
        mid=root
        for i in range(mid_idx+1):
            mid=mid.next

        # 中间节点后续半分，逆转
        reverse=mid.next
        before_reverse=None
        while reverse:
            next_reverse=reverse.next
            reverse.next=before_reverse
            before_reverse=reverse
            reverse=next_reverse
        mid.next=None

        # 轮流遍历，构建新的节点
        old_temp=head.next
        reverse_temp=before_reverse
        res_temp=head
        swt=True
        while old_temp or reverse_temp:
            swt=not swt
            if swt:
                if not old_temp:
                    continue
                res_temp.next=old_temp
                old_temp=old_temp.next
                res_temp=res_temp.next
            else:
                if not reverse_temp:
                    continue
                res_temp.next=reverse_temp
                reverse_temp=reverse_temp.next
                res_temp=res_temp.next
            # print(res_temp.val)

        pass

if __name__=='__main__':
    nums=[1,2,3,4]
    head=create_list_node(nums)

    sol=Solution()
    sol.reorderList(head)
    arr=calc_arr(head)
    print(arr)
    
    pass